#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <cstdlib>
using namespace std;

/*
 *list defition and operation
 */
struct ListNode
{
        int val;
        ListNode *next;
        ListNode(int x): val(x), next(NULL){}
};

ListNode *make_list(int a[],int n)
{
    if(!n) return NULL;
    ListNode *head = new ListNode(a[0]), *p = head;
    for (int i=1; i < n; ++i)
    {
        p->next = new ListNode(a[i]);
        p = p->next;
    }

    return head;
}

void print_list(ListNode *head)
{
    cout << "Print List:" <<endl;
    while(head!=NULL){
        cout << head->val <<" ";
        head = head->next;
    }
    cout << endl;
}

ListNode *reverse_list(ListNode *head) 
{
    if(head == NULL || head->next == NULL) return NULL;
    ListNode **p = &head, *q, *r;
    q = *p;
    while(q->next!=NULL) {
        r = q->next;
        q->next = r->next;
        r->next = *p;
        *p = r;
    }
    return head;
}

void delete_list(ListNode *head)
{
        ListNode *p;
        while(head!=NULL){
                p = head->next;
                delete head;
                head = p;
        }
}

void make_list_cycle(ListNode *head, int index)
{
        if(index<=0||head==NULL) exit(0);

        ListNode *p = head;
        while(head->next!=NULL) head = head->next;
        while(--index&&p!=NULL) p = p->next;

        if(p==NULL) exit(0);
        else head->next = p; 
}


/*
 *Binary Tree defition and operation
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void print_vector(vector<vector<int> > v)
{
    cout << "Print Vector:" << endl;
    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
            cout << v[i][j]<<" ";
        }
        cout << endl;
    }
}

void print_vector(vector<int> v)
{
    cout << "Print Vector:" << endl;
    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;
}

TreeNode * build_binary_tree(vector<int> v)
{
    queue<TreeNode *> q;
    TreeNode *root = new TreeNode(v[0]);
    q.push(root);

    TreeNode *p = NULL;
    for (int i = 1; i < v.size(); ) {
        p = q.front();
        q.pop();

        if (v[i]!=-1) {
            p->left = new TreeNode(v[i]);
            q.push(p->left);
        }
        i++;
        if (v[i]!=-1) {
            p->right = new TreeNode(v[i]);
            q.push(p->right);
        }
        i++;
    }
    return root;
}

vector<vector<int> > levelOrder(TreeNode *root){
    queue<TreeNode *> q;
    queue<int> level_q;
    vector<vector<int> > v;
    TreeNode *p = NULL;
    int level;

    q.push(root);
    level_q.push(0);

    while(!q.empty()) {
        p = q.front();
        q.pop();
        level = level_q.front();
        level_q.pop();

        if (v.size()<=level) {
            vector<int> sub_vec;
            sub_vec.push_back(p->val);
            v.push_back(sub_vec);
        } else {
            v[level].push_back(p->val);
        }

        if (p->left != NULL) {
            q.push(p->left);
            level_q.push(level+1);
        }
        if (p->right != NULL) {
            q.push(p->right);
            level_q.push(level+1);
        }
    }

    return v;
}
